class QuickSort:
    def __init__(self, list_target):
        self.__list = list_target

    def __sub_sort(self, low, high):
        key = self.__list[low]
        while low < high:
            # 后面的数向前甩
            while low < high and self.__list[high] > key:
                high -= 1
            self.__list[low] = self.__list[high]
            # 前面的数向后甩
            while low < high and self.__list[low] < key:
                low += 1
            self.__list[high] = self.__list[low]
        self.__list[low] = key
        return low

    def __sort_inner(self, low, high):
        if low < high:
            key = self.__sub_sort(low, high)
            self.__sort_inner(low, key - 1)
            self.__sort_inner(key + 1, high)

    def sort(self):
        self.__sort_inner(0,len(self.__list)-1)

    def print(self):
        for item in self.__list:
            print(item, end=' ')
        print()


if __name__ == '__main__':
    quick_sort = QuickSort([4, 1, 2, 6, 7, 3, 9, 8])
    quick_sort.sort()
    quick_sort.print()
